package graph

import (
	"gitee.com/yrwy/msgo/pkg/mem/stl"
)

// 如果生成树是从起点开始遍历的结果
// 则每次Set的都是子节点对应的父节点，每次Get的都是子节点的父节点
// eg: GetS2D[T](t, start, end)返回从起点到终点的路径, GetD2S[T](t, start, end)返回从终点到起点的路径
// 如果生成树是从终点开始遍历
// GetS2D[T](t, end, start) 返回从终点到起点的路径，GetD2S[T](t, end, start)返回从起点到终点的路径
type Tree[T comparable] interface {
	Get(next T) (T, bool)
	Set(next, prev T)
}

func GetS2D[T comparable](t Tree[T], src, dst T) []T {
	r := GetD2S[T](t, src, dst)
	r = stl.SliceReverse(r)
	return r
}

func GetFitS2D[T comparable](t Tree[T], src, dst T) []T {
	r := GetFitD2S[T](t, src, dst)
	r = stl.SliceReverse(r)
	return r
}

func GetD2S[T comparable](t Tree[T], src, dst T) []T {
	n, ok := t.Get(dst)
	if ok {
		var r []T
		r = append(r, dst)
		for ok && n != src {
			r = append(r, n)
			n, ok = t.Get(n)
		}
		if ok {
			r = append(r, src)
			return r
		}
		return nil
	}
	return nil
}

func GetFitD2S[T comparable](t Tree[T], src, dst T) []T {
	n, ok := t.Get(dst)
	if ok {
		var r []T
		for ok && n != src {
			r = append(r, n)
			n, ok = t.Get(n)
		}
		if ok {
			return r
		}
		return nil
	}
	return nil
}

type GraphMapTree[T comparable] map[T]T

func (x GraphMapTree[T]) Get(next T) (T, bool) {
	r, ok := x[next]
	return r, ok
}

func (x GraphMapTree[T]) Set(next, prev T) {
	x[next] = prev
}
